package site.wanjiahao.sort.uncompare;

import site.wanjiahao.sort.Sort;

// 计数排序
public class CountingSort1 extends Sort<Integer> {


    @Override
    protected void sort() {
        int max = getMax();
        int[] ints = new int[max];
        for (int e : array) {
            ints[e] += 1;
        }
        // 覆盖数据
        int index = 0;
        for (int i = 0; i < ints.length; i++) {
            while (ints[i]-- > 0) {
                array[index++] = i;
            }
        }
    }

    private int getMax() {
        int max = 0;
        for (int e : array) {
            if (max < e) {
                max = e;
            }
        }
        return max + 1;
    }

}
